package leetcode.erfen;

/**
 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

 如果数组中不存在目标值 target，返回[-1, -1]。

 输入：nums = [5,7,7,8,8,10], target = 8
 输出：[3,4]

 */
public class SearchRange34 {
    public static void main(String[] args) {
        int [] arr = new int[]{5,7,7,8,8,10};
        int ints = new SearchRange34().binSearch(arr,7);
        System.out.println(ints);
    }

    public int[] searchRange(int[] nums, int target) {
        if(nums.length==0) return  new int []{-1,-1};

        int upper = upperBound(nums, target);//上界的后一位   upper-1
        int lower = lowerBound(nums, target);//下界的前一位  lower+1

        if(lower+1 == nums.length || upper-1==-1 ||nums[lower+1]!=target || nums[upper-1]!=target )
            return  new int []{-1,-1};

        return new int []{lower+1,upper-1};
    }

    private int upperBound(int [] nums,int taget){
        int l=0,r= nums.length-1;
        while (l<=r){
            int mid = l+(r-l)/2;
            if(nums[mid]>taget)
                r = mid-1;
            else
                l = mid+1;
        }
        return l;//返回上界的后一位
    }

    //[l...r]闭区间范围内找
    private int lowerBound(int [] nums,int taget){
        int l=0,r= nums.length-1;
        while (l<=r){
            int mid = l+(r-l)/2;
            if(nums[mid]>=taget)
                r = mid-1;
            else
                l = mid+1;
        }
        return r;//返回下界的前一位
    }

    //[l...r]闭区间范围内找
    private int binSearch(int [] nums,int taget){
        int l=0,r= nums.length-1;
        while (l<=r){
            int mid = l+(r-l)/2;
            if(nums[mid]==taget)
                return mid;
            if(nums[mid]>taget)
                r = mid-1;
            else
                l = mid+1;
        }
        return -1;
    }
}